package off;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lj
 * @Description: 杨辉三角 方法：动态规划
 * @date 2020-10-24 21:39
 * @QQ 851477108
 */


public class YHsan {
    public static void main(String[] args) {
    }

    class Solution{
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> triangle = new ArrayList<List<Integer>>();
            //第一个情况，用户请求0行，那么他们得到0行
            if (numRows == 0){
                return triangle;
            }

            //第二个情况，第一行总是[1]
            triangle.add(new ArrayList<>());
            triangle.get(0).add(1);

            for (int i = 1; i < numRows; i++) {
                //行
                List<Integer> row = new ArrayList<>();
                //上一行
                List<Integer> prevRow = triangle.get(i - 1);

                //第一行元素始终为1
                row.add(1);

                //每个三角形元素(除了每行的第一个和最后一个)
                //等于上面和左边的元素的和
                // above-and-to-the-right
                for (int j = 1; j < i; j++) {
                    row.add(prevRow.get(j-1) + prevRow.get(j));
                }

                //The last row element is always 1.
                row.add(1);
                triangle.add(row);

            }
            return triangle;
        }
    }
}
